package algorithm.h23d_p17;

import java.util.Arrays;

//1.给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最 大矩形，并返回其面积。
public class FindMaxArea {
    /**
     * input：array[][]
     * return: int 最大面积值
     */
    public static int FindMaxAreaTwoDimention(int [][] matrix){
        // 判断输入矩阵是否为空
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int max=0;
        int rowsLength=matrix.length;
        int colsLength=matrix[0].length;
        //matrixArea 矩阵面积，用于存储每个值向右和向下扩展的值
        int[][] matrixArea=new int[rowsLength][colsLength];
//        需要获取坐标，不使用matrix.for遍历
        for (int i = 0; i < rowsLength; i++) {
            for (int j = 0; j < colsLength; j++) {
                //获取面积值
                matrixArea[i][j]=getArea(matrix,i,j);
            }
        }
        for (int[] ints : matrixArea) {
            for (int anInt : ints) {
                max=max>anInt ?max:anInt;
            }
        }
//        System.out.println(Arrays.deepToString(matrixArea));
        for (int[] ints : matrixArea) {
            System.out.println(Arrays.toString(ints));
        }
        return max;
    }
    /**
     * input：array[][], index i j
     * return: int 最大面积值
     */
    private static int getArea(int[][] matrix, int i, int j) {
        if (matrix[i][j]==0)
            return 0;
//        横向遍历
        int length=1,high=1;
        int area_1=1,area_2=1;
        while (true){
            j+=1;
            if (j==matrix[0].length||matrix[i][j]==0)
                break;
            length++;
        }
        j=j-length;
//        纵向遍历，以length为基础
        lo:while (true){
            i++;
            if (i==matrix.length||matrix[0].length==1)
                break;
            for (int k = 0; k < length; k++) {
                if (j+k>=matrix[0].length||matrix[i][j+k]==0)
                    break lo;
            }
            high++;
        }
        i=i-high;
        area_1=length*high;

        //上述获取的是 横长方形遍历方式，下面进行竖长方形
        length=1;
        high=1;
//        纵向遍历
        while (true){
            i+=1;
            if (i==matrix.length||matrix[i][j]==0)
                break;
            high++;
        }
        i=i-high;
        lo:while (true){
            j++;
            if (j==matrix[0].length||matrix.length==1)
                break;
            for (int k = 0; k < high; k++) {
                if (i+k>=matrix.length||matrix[i+k][j]==0)
                    break lo;
            }
            high++;
        }
        i=i-length;
        area_2=length*high;


        return Math.max(area_1,area_2);
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {0, 1, 1, 1},
                {0, 1, 0, 1},
                {0, 1, 1, 1}

        };
        System.out.println("矩阵面积的最大值为："+FindMaxAreaTwoDimention(matrix));
    }
}
